<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-07 17:35:41
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-08 14:56:34
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树统一迭代方法</title>
</head>

<body>
    <ul>
        <li>统一迭代法：前序遍历</li>
        <li></li>
        <li></li>
        <li></li>
    </ul>
    <script>
        class Node {
            constructor(root, left, right) {
                this.root = root || null;
                this.left = left || null;
                this.right = right || right;
            }
            //前序遍历 入栈：右-左，出栈：中-左-右
            preOrderTraversal(root, res = []) {
                if (!root) {
                    return res;
                }
                const stack = [root];
                let cur = null;
                while (stack.length) {
                    cur = stack.pop();
                    res.push(cur.root);
                    cur.right && stack.push(cur.right);
                    cur.left && stack.push(cur.left);
                }
                return res;
            }
            //中序遍历 入栈：左-右，出栈：左-中-右
            inOrderTraversal(root, res = []) {
                let stack = [];
                let cur = root;
                while (stack.length || cur) {
                    if (cur) {
                        stack.push(cur);
                        cur = cur.left;
                    } else {
                        cur = stack.pop();
                        res.push(cur.root);
                        cur = cur.right;
                    }
                }
                return res;
            }
            //后序遍历 入栈：左-右，出栈：中-左-右
            postOrderTraversal(root, res = []) {
                if (!root) {
                    return res;
                }
                const stack = [root];
                let cur = null;
                do {
                    cur = stack.pop();
                    res.push(cur.root);
                    cur.left && stack.push(cur.left);
                    cur.right && stack.push(cur.right);
                } while (stack.length);
                return res.reverse();
            }
        }
        // 迭代遍历

    </script>
</body>

</html>